
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
#include <vector>
#include <queue>
#include <deque>
using namespace std;
class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        if (!root)
            return {};
        queue<TreeNode *> q;
        vector<vector<int>> ans;
        q.push(root);
        int num = 1;
        bool change = 0;
        while (q.size())
        {
            deque<int> tmp;
            while (num--)
            {
                auto tt = q.front();
                tmp.push_back(tt->val);
                if (tt->left)
                    q.push(tt->left);
                if (tt->right)
                    q.push(tt->right);
                q.pop();
            }
            vector<int> copy(tmp.begin(), tmp.end());
            if (change)
                reverse(copy.begin(), copy.end());
            change = !change;
            ans.push_back(move(copy));
            num = q.size();
        }
        return ans;
    }
};